WC2021 表达式求值题解 2023-01-01 00:00 folder 题解Solution label 中文Chinese, 归档Archived, 信竞OI

题目难度: 省选+

题目分类: 计数

题目大意: [WC2021] 表达式求值

定义二元操作符 < 和 > 操作与两个长度都为 \(n\) 的数组 A, B

A < B = C, \(C[i] = \min(A[i],B[i])\) \((1≤i≤n)\)

A > B = C, \(C[i] = \max(A[i],B[i])\) \((1≤i≤n)\)

给 \(m\) (m≤10) 个长度为 \(n\) 的整数数组, 记为 \(A_0, A_1 ... A_{m-1}\)

给一带计算的中序表达式 \(E\), 其中每个元素都属于 \(A\), 每个操作都属于 < 和 > 或者 ?, ? 代表可能是 < 或者 > （例如1?0>2?0)

求所有可能的结果数组每一项之和之和, 其中若有 \(c\) 个 ?, 则一共有 \(2^c\) 中结果数组

题目答案:

数组每个下标对答案的贡献独立, 考虑单次查询

其中结果数组的每个位置必然是 A 当中出现过的值, 假设结果数组中出现的是第 i 的数组的值

可以发现, i 的结果和 \(A_j\) 中其他元素的大小关系有关, 若枚举 i, 此时转化成了一个计数问题

如果直接选择枚举顺序是 m!, 但考虑到只需要 \(A_j\) 中其他元素和目前枚举的 \(A_i\) 的大小关系即可

状态压缩后树上DP即可解决

#include"bits/stdc++.h"
using namespace std;


const int maxn = 5e4+5;
const int MOD = 1e9+7;
int f[1<<10][maxn][2];
int ans;
int n,m;
int a[15][maxn];
int bas;
int c[maxn];
int idx;
int ls[maxn],rs[maxn];
int val[maxn],sta[maxn];
int op[maxn],top,tp,rt;
string s;
pair<int,int> u[15];

void check () { 
    while (~op[top]) {
        val[++idx] = -op[top--];
        ls[idx] = sta[tp-1];
        rs[idx] = sta[tp],
        sta[--tp] = idx;
    }
}
void DFS (int x) {
	if (val[x]>=0) {
        for (int S=0;S<=bas;S++) {
            if ((S>>val[x])&1) f[S][x][0] = 1;
            else f[S][x][1] = 1; 
        }
        return;
    }
	DFS(ls[x]);
    DFS(rs[x]);
	for(int S=0;S<=bas;S++) {
		if (-1==val[x]) {
			f[S][x][1] = 1ll*f[S][ls[x]][1]*f[S][rs[x]][1]%MOD,
			f[S][x][0] = (1ll*(f[S][ls[x]][0]+f[S][ls[x]][1])*(f[S][rs[x]][0]+f[S][rs[x]][1])-f[S][x][1])%MOD;
        }
        else if (-2==val[x]) {
			f[S][x][0] = 1ll*f[S][ls[x]][0]*f[S][rs[x]][0]%MOD,
			f[S][x][1] = ((1ll*f[S][ls[x]][0]+1ll*f[S][ls[x]][1])*(f[S][rs[x]][0]+f[S][rs[x]][1])-f[S][x][0])%MOD;
        }
        else {
            f[S][x][0] = (1ll*f[S][ls[x]][0]*f[S][rs[x]][0]*2+1ll*f[S][ls[x]][0]*f[S][rs[x]][1]+1ll*f[S][ls[x]][1]*f[S][rs[x]][0])%MOD,
			f[S][x][1] = (1ll*f[S][ls[x]][1]*f[S][rs[x]][1]*2+1ll*f[S][ls[x]][0]*f[S][rs[x]][1]+1ll*f[S][ls[x]][1]*f[S][rs[x]][0])%MOD;
        }
    }
}
void calc(int x){
	for (int i=0;i<m;i++) u[i] = make_pair(a[i][x],i);
    sort(u,u+m);
    int S=0;
	for (int i=0;i<m;i++) {
        ans += 1ll*(f[S][rt][1]-f[S+(1<<u[i].second)][rt][1])*u[i].first%MOD;
        S |= 1<<u[i].second;
        ans %= MOD;
    }
}
int main() {
	cin>>n>>m;
    bas = (1<<m)-1;
    op[0] = ~0;
	for(int i=0;i<m;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
	cin>>s;
    int len = s.size();
    s = "#"+s;
	for(int i=1;i<=len;i++) {
		if (s[i]=='(') op[++top] = -1;
		else if (s[i]=='<') op[++top] = 1;
		else if (s[i]=='>') op[++top] = 2;
		else if (s[i]=='?') op[++top] = 3;
		else if (s[i]==')') top--,check();
		else {
            val[sta[++tp]=++idx] = s[i]-'0';
            check();
        }
    }
	  rt = sta[tp];
    DFS(rt);
    for (int i=1;i<=n;i++) calc(i);
    ans = (ans%MOD+MOD)%MOD;
    cout<<ans<<endl;
}